class Solution {
    public int[] countBits(int n) {
        //一次遍历
        int[] res = new int[n + 1];
        for (int i = 1; i < res.length; i++) {
            if ((i & 1) == 1)
                res[i] = res[i / 2] + 1;
            else
                res[i] = res[i / 2];
        }
        return res;
    }
}
